#pragma once
#include <vector>
#include <list>

using std::vector;
using std::list;

namespace my_hash
{
	// hash表中每个元素的状态
	enum STAT
	{
		EMPTY,
		DELETE, // 删除
		EXIST   // 存在
	};
	template<typename Val>
	struct HashNode
	{
		HashNode()
			:_next(nullptr)
		{}
		HashNode(Val kv)
			:_kv(kv),
			_next(nullptr)
		{}
		Val _kv;
		HashNode<Val>* _next; // 是哈希桶所用的结构
	};

	template<typename K, typename Val, typename KeyOfVal, typename HashFun>
	class Hash;

	template<typename K, typename Val, typename Ptr, typename Ref, typename KeyOfVal, typename HashFun>
	struct hash_iterator
	{
		typedef hash_iterator<K, Val, Ptr, Ref, KeyOfVal, HashFun> Self;
		typedef hash_iterator<K, Val, Val*, Val&, KeyOfVal, HashFun> iterator;
		typedef Hash<K, Val, KeyOfVal, HashFun> Hash_;

		hash_iterator(Hash_* hash)
			:_hash(hash)
		{}
		hash_iterator(const HashNode<Val>* node, Hash_* hash)
			:_node(const_cast<HashNode<Val>*>(node)),
			_hash(hash)
		{}
		hash_iterator(const iterator& it)
			:_node(it._node),
			_hash(it._hash)
		{}

		Ptr operator->()
		{
			return &_node->_kv;
		}
		Ref operator*()
		{
			return _node->_kv;
		}
		Self& operator++()
		{
			KeyOfVal kov;
			size_t i_hash = _hash->HashFunc(kov(_node->_kv));
			HashNode<Val>* cur = _hash->_hash_but[i_hash];
			while (cur->_kv != _node->_kv)
			{
				cur = cur->_next;
			}
			HashNode<Val>* next = cur->_next;
			if (next == nullptr)
			{
				//向表的后面去找下一个有效的节点，找不到后直接为nullptr
				for (int i = i_hash + 1; i < _hash->_cap; i++)
				{
					if (_hash->_hash_but[i])
					{
						next = _hash->_hash_but[i];
						break;
					}
				}
			}
			_node = next;
			return *this;

		}

		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		HashNode<Val>* _node;
		const Hash_* _hash;
	};
	// KeyOfVal：unordered_map,unordered_set复用hash时获取pair的key
	// HashFunc：当传入自定义类型时需要提供自定义的哈希函数，将key转换为数
	template<typename K, typename Val, typename KeyOfVal, typename HashFun>
	class Hash
	{
		// 模板类的友元
		template<typename K, typename Val, typename Ptr, typename Ref, typename KeyOfVal, typename HashFun>
		friend struct hash_iterator;
	public:
		typedef HashNode<Val> Node;
		typedef Hash<K, Val, KeyOfVal, HashFun> Self;
		typedef hash_iterator<K, Val, Val*, Val&, KeyOfVal, HashFun> iterator;
		typedef hash_iterator<K, Val, const Val*, const Val&, KeyOfVal, HashFun> const_iterator;


	private:
		void swap(Hash& h)
		{
			_hash_but.swap(h._hash_but);
			_cap = h._cap;
			_sz = h._sz;
		}

		Node* get_node(Val kv)
		{
			return new Node(kv);
		}

		void addSpace_Bucket()
		{
			int newcap = _cap == 0 ? 10 : _cap * 2;
			Hash<K, Val, KeyOfVal, HashFun> tmp(newcap);
			for (int i = 0; i < _cap; i++)
			{
				Node* cur = _hash_but[i];
				while (cur)
				{
					tmp.insert(cur->_kv);
					cur = cur->_next;
				}
			}
			swap(tmp);
		}

		std::pair<iterator, bool> insert_Bucket(Val kv)
		{
			KeyOfVal kov;
			Node* res = find_Bucket(kov(kv)).first;
			if (res != nullptr)
			{
				iterator it(res, this);
				return std::make_pair(it, false);
			}
			//return std::make_pair(iterator(res, this), false);
		// 哈希桶的扩容方案是：如果当前的个数 与 哈希桶的个数相同则进行扩容
			if (_sz >= _cap)
				addSpace_Bucket();
			size_t i_hash = HashFunc(kov(kv));
			Node* cur = get_node(kv);
			// 进行头插 O(1)
			// 创建哨兵位头节点的
			Node* head = get_node(Val());
			head->_next = _hash_but[i_hash];

			cur->_next = head->_next;
			head->_next = cur;
			_hash_but[i_hash] = head->_next;
			delete head;
			_sz++;
			// 编译器会把(iterator(cur, this), true)当作initializer list
			// 
			iterator it(cur, this);
			return std::make_pair(it, true);
		}


		iterator erase_Bucket(const_iterator pos)
		{
			KeyOfVal kov;
			auto p = find_Bucket(kov(pos._node->_kv));
			Node* cur = p.first;
			if (cur == nullptr)
				return iterator(nullptr, this);
			size_t i_hash = HashFunc(kov(pos._node->_kv));
			iterator res(pos._node, this);
			++res;
			Node* head = get_node(Val());
			head->_next = _hash_but[i_hash];
			Node* pre = p.second == cur ? head : p.second;
			pre->_next = cur->_next;
			_hash_but[i_hash] = head->_next;
			delete cur;
			delete head;
			_sz--;
			return res;
		}

		std::pair<Node*, Node*> find_Bucket(const K& key) const
		{
			KeyOfVal kov;

			size_t i_hash = HashFunc(key);
			Node* cur = _hash_but[i_hash];
			Node* pre = cur;
			while (cur && kov(cur->_kv) != key) // 自定义类型需要提供!=
			{
				pre = cur;
				cur = cur->_next;
			}
			return std::make_pair(cur, pre);
		}

		Node* first()
		{
			for (auto cur : _hash_but)
			{
				if (cur)
					return cur;
			}
			return nullptr;
		}

		// 将key 转化为 hash下标
		size_t HashFunc(const K& key) const
		{
			// 直接假设 key是整形 如果是其他类型 肯定是需要先将key 转换为 size_t类型 在求hash下标
			size_t n_key = HashFun()(key);
			return n_key % _cap;
		}



	public:
		Hash(size_t cap = 10)
			:_cap(cap),
			_sz(0)
		{
			_hash_but.resize(cap, nullptr);
		}


		iterator begin()
		{
			return iterator(first(), this);
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin() const
		{
			return const_iterator(first(), this);
		}
		const_iterator end() const
		{
			return const_iterator(nullptr, this);
		}


		std::pair<iterator, bool> insert(Val kv)
		{
			return insert_Bucket(kv);
		}
		iterator erase(const_iterator pos)
		{
			return erase_Bucket(pos);
		}
		iterator find(const K& key)
		{
			Node* aim = find_Bucket(key).first;
			return iterator(aim, this);

		}
	private:
		vector<Node*> _hash_but; // 使用哈希桶存储元素
		size_t _cap; // 哈希桶的个数,线性探测的地址长度
		size_t _sz; //  实际存放多少个元素
	};

}